//: [Previous](@previous)

/*:
 
 ### leetcode上第209号问题: Minimum Size Subarray Sum
 https://leetcode.com/problems/minimum-size-subarray-sum/submissions/
 ```
 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
 示例:
 输入: s = 7, nums = [2,3,1,2,4,3]
 输出: 2
 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
 ```
 */

import Foundation

var s = 7, nums = [2,3,1,2,4,3]
s = 11
nums = [1,2,3,4,5]

// 1. 遍历 90.57%
// 时间复杂度 O(n)
// 控件复杂度 O(1)
func Solution(_ nums: [Int], _ s: Int) -> (Int, Int) {
    var l = 0, r = 0, sum = 0
    var index = 0, length = nums.count + 1
    while l < nums.count {
        if r < nums.count && sum < s {
            sum += nums[r]
            r += 1
        } else  {
            sum -= nums[l]
            l += 1
        }
        if sum == s {
            if length > r - l {
                length = r - l
                index = l
            }
        }
    }
    if length == nums.count + 1 {
        return (-1, -1)
    }
    return (index, length)
}
print("1. \(Solution(nums, s))")


// 100%
// 时间复杂度 O(n) for 循环执行n此  但是while循环只执行n次，而不是每次都循环n次
// 控件复杂度 O(1)
func Solution2(_ s: Int, _ nums: [Int]) -> Int {
    var l = 0, sum = 0
    var length = nums.count + 1
    for i in 0..<nums.count {
        sum += nums[i]
        while sum >= s {
            length = min(length, i - l + 1)
            sum -= nums[l]
            l += 1
        }
    }
    return length == nums.count + 1 ? 0 : length
}
Solution2(s, nums)


//: [Next](@next)
